package com.leetcode.No3176;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

public class Solution {

    @Test
    public void test() {
//        int[] nums = new int[]{1,2,1,1,3};
//        int k = 2;
//        int[] nums = new int[]{1,2,3,4,5,1};
//        int k = 0;
        int[] nums = new int[]{1,17};
        int k = 0;
        System.out.println("ans = " + maximumLength(nums, k));
    }

    public int maximumLength(int[] nums, int k) {
        LinkedList<Node> list = new LinkedList<>();
        Node currentNode = null;
        Map<Integer, Integer> totalCountMap = new HashMap<>();
        for (int num : nums) {
            if (currentNode == null || currentNode.key != num) {
                currentNode = new Node(num);
                list.add(currentNode);
            } else {
                currentNode.addCount();
            }
            Integer totalCount = totalCountMap.getOrDefault(num, 0);
            totalCountMap.put(num, totalCount + 1);
        }

        if (list.size() <= (k + 1)) {
            return nums.length;
        }

        for (int i = 0; i < list.size(); i++) {
            Node node = list.get(i);
            if (i > 0) {
                node.pre = list.get(i - 1);
            }
            if (i < list.size() - 1) {
                node.next = list.get(i + 1);
            }
        }


        ArrayList<Node> sortList = new ArrayList<>(list);
        sortList.sort((n1, n2) -> {
            if (n1.key == n2.key) {
                return n1.count - n2.count;
            }
            if (totalCountMap.get(n1.key) == totalCountMap.get(n2.key)) {
                return n1.key - n2.key;
            }
            return totalCountMap.get(n1.key) - totalCountMap.get(n2.key);
        });

        for (Node node : sortList) {

//            System.out.println(Arrays.toString(list.stream().map(n -> n.key).toArray()));

            list.remove(node);
            if (node.pre != null) { node.pre.next = node.next; }
            if (node.next != null) { node.next.pre = node.pre; }
            if (node.pre != null && node.next != null && node.pre.key == node.next.key) {
                node.pre.count += node.next.count;
                list.remove(node.next);
            }

            if (list.size() <= (k + 1)) {
                break;
            }
        }

        int result = 0;
        for (Node node : list) {
            result += node.count;
        }

        return result;
    }

    public class Node {
        int key;
        int count;
        Node pre = null;
        Node next = null;
        public Node(int key) {
            this.key = key;
            this.count = 1;
        }
        public void addCount() {
            ++count;
        }
    }

    public static void main(String[] args) {
        String str = "1145474\n" +
                "1143244\n" +
                "1142756\n" +
                "1140247\n" +
                "1131415\n" +
                "1143660\n" +
                "1125078\n" +
                "1143460\n" +
                "1137076\n" +
                "1135473\n" +
                "1131063\n" +
                "1140079\n" +
                "1145146\n" +
                "1145489\n" +
                "1142181\n" +
                "1139211\n" +
                "1130702\n" +
                "1135873\n" +
                "1131151\n" +
                "1124822\n" +
                "1144960\n" +
                "1140381\n" +
                "1137082\n" +
                "1141740\n" +
                "1140245\n" +
                "1130194\n" +
                "1125972\n" +
                "1127370\n" +
                "1131836\n" +
                "1131923\n" +
                "1132314\n" +
                "1135524\n" +
                "1140362\n" +
                "1139522\n" +
                "1136174\n" +
                "1143720\n" +
                "1136982\n" +
                "1142391\n" +
                "1135886\n" +
                "1145398\n" +
                "1141966\n" +
                "1136224\n" +
                "1130360\n" +
                "1135897\n" +
                "1138935\n" +
                "1139146\n" +
                "1142480\n" +
                "1136173\n" +
                "1134832\n" +
                "1140829\n" +
                "1144423\n" +
                "1139870\n" +
                "1145422\n" +
                "1129740\n" +
                "1138018\n" +
                "1129921\n" +
                "1130904\n" +
                "1139053\n" +
                "1144362\n" +
                "1133702\n" +
                "1129293\n" +
                "1124697\n" +
                "1138041\n" +
                "1130190\n" +
                "1138042\n" +
                "1131378\n" +
                "1143643\n" +
                "1144877\n" +
                "1129203\n" +
                "1137001\n" +
                "1138688\n" +
                "1144598\n" +
                "1131233\n" +
                "1141613\n" +
                "1136247\n" +
                "1132812\n" +
                "1135733\n" +
                "1138439\n" +
                "1140003\n" +
                "1124245\n" +
                "1133120\n" +
                "1136538\n" +
                "1128812\n" +
                "1142851\n" +
                "1125116\n" +
                "1136096\n" +
                "1126025\n" +
                "1131183\n" +
                "1132196\n" +
                "1134142\n" +
                "1135381\n" +
                "1123048\n" +
                "1143039\n" +
                "1143529\n" +
                "1135352\n" +
                "1129740\n" +
                "1138018\n" +
                "1129921\n" +
                "1130904\n" +
                "1139053\n" +
                "1132196\n" +
                "1134142\n" +
                "1135381\n" +
                "1123048\n" +
                "1143039\n" +
                "1143529\n" +
                "1135352\n" +
                "1137849\n" +
                "1144034\n" +
                "1141686\n" +
                "1130193\n" +
                "1135238\n" +
                "1130909\n" +
                "1142270\n" +
                "1141776\n" +
                "1142208\n" +
                "1127475\n" +
                "1135539\n" +
                "1140121\n" +
                "1135615\n" +
                "1135373\n" +
                "1141713\n" +
                "1130529\n" +
                "1125665\n" +
                "1144033\n" +
                "1137767\n" +
                "1135372\n" +
                "1137157\n" +
                "1136230\n" +
                "1127477";
        System.out.println(str.replaceAll("\n", ","));
    }
}
